#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Solution:
    """
    @param A: An array of integers
    @return: An integer
    """
    def firstMissingPositive(self, A):
        # write your code here
        A = [i for i in A if i > 0]
        if not A:
            return 1

        max_n = min_n = A[0]

        for i in range(1, len(A)):
            n = A[i]
            if n < 0:
                continue

            if n < min_n:
                if n == min_n - 1:
                    min_n = n
                else:
                    return n + 1
            if n > max_n:
                if n == max_n + 1:
                    max_n = n
                else:
                    return max_n + 1

        if min_n > 1:
            return min_n - 1
        if max_n > 0:
            return max_n + 1
        return 1


def main():
    print("start main")
    s = Solution()
    # l = [3,4,-1,1]
    l = [1, 2, 0]
    ret = s.firstMissingPositive(l)
    print(ret)

if __name__ == "__main__":
    main()
